/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package prim;

import static aux.General.extractWeight;
import static aux.General.infinity;
import aux.MinHeap;
import base.JGrafo;
import base.Vertice;
import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.HashMap;


/**
 *
 * @author diego
 */
public class PRIM {
    
    public static ArrayList<AbstractMap.SimpleEntry<Vertice, Vertice>> mst_prim (JGrafo G, HashMap<AbstractMap.SimpleEntry<Vertice, Vertice>, Integer> weights, Vertice s) {
        ArrayList<AbstractMap.SimpleEntry<Vertice, Vertice>> S = new ArrayList<>();
        HashMap<Vertice, Vertice> P = new HashMap <>();
        for (Vertice v : G.vertices) {
            v.key = infinity;
            P.put(v, null);
        }
        s.key = 0;
        MinHeap<Vertice> Q = new MinHeap<>(G.vertices);
        while (Q.size() != 0) {
            Vertice u = Q.pop();
            if (P.get(u) != null) {
                AbstractMap.SimpleEntry <Vertice, Vertice> tuple = new AbstractMap.SimpleEntry<>(P.get(u), u);
                S.add(tuple);
            }
            for (Vertice v : G.adjacencies(u)) {
                int w = extractWeight(u, v, weights);
                if (Q.contains(v) && extractWeight(u, v, weights) < v.key) {
                    v.key = extractWeight(u, v, weights);
                    P.put(v, u);
                }
            }
        }
        return S;
    }
}
